
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 第一遍 3/1
     * 【主要找不符合的类型】
     * 当遇到左括号时入栈，遇到右括号时出栈，
     * 比较出栈元素是否与右括号匹配，最终判断栈是否为空。
     * @param s
     * @return
     */
//    public boolean isValid(String s) {
//        if (s == null || s.length() == 0) return true;
//
//        // 栈：先进先出
//        Stack<Character> stack = new Stack<Character>();
//        for (char c : s.toCharArray()) {
//            if (c == '(' || c == '[' || c == '{') {
//                stack.push(c);
//            } else {
//                if (stack.isEmpty()) {
//                    return false;
//                }
//                char pop_c = stack.pop();
//                if (pop_c == '(' && c != ')' || pop_c == '[' && c != ']' || pop_c == '{' && c != '}') {
//                    return false;
//                }
//            }
//        }
//        return stack.isEmpty();
//    }


    /**
     * 第二遍 3/7
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;

        // 使用栈保存括号
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char pop_c = stack.pop();
                if (pop_c == '(' && c != ')' || pop_c == '[' && c != ']' || pop_c == '{' && c != '}') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }


}
//leetcode submit region end(Prohibit modification and deletion)
